When routing is applied in a wireless communications network, such a network is often denoted a multihop network. In a multihop network, nodes or stations out of reach from each other can benefit from intermediate located nodes that can forward their messages from the source node towards the destination node. Traditionally, multihop networks have been associated with so called ad hoc networks, where nodes are mostly mobile and no central coordinating infrastructure exists. However, the idea of multihop networking can also be applied when nodes are fixed and/or a central coordinating infrastructure exists. One such scenario targets rural area Internet access and uses fixed nodes attached to the top of house roofs, lamp posts and so forth.
So called Bellman-Ford and other prior art routing techniques build up and define a multihop tree or route from a source node to a destination node in a communication network. This is performed by means of passing routing cost information through the network to form routing tables based on the cost information. This cost information can include for example, message delays, cumulative power consumption, or hop count. Within the system, each node or station uses its routing table to make independent decisions. Bellman-Ford based routing leads to the existence of a single route for each source-destination node pair. However as topology changes due to mobility, this single route will pass different nodes over time.
There are several other reasons why a topology changes over time in addition to moving nodes. For example, topology changes may occur even without nodes moving; such as variations caused by moving objects on which radio waves reflect or changes in the communication media. These topology changes include, for example, channel variations, traffic pattern changes, and transmit pattern changes and resource allocation changes.
Changes or fluctuations within the system imply that optimal routing can change based on current conditions in the system. In other words, fluctuations of system properties or characteristics over time, can create windows of opportunity that enable signal transmissions to be more successful than at other times and for other conditions. System properties subjected to change can include, for example, path quality, noise, interference, and message traffic load. The prior art routing techniques such as Bellman-Ford, do not recognize these windows of opportunity, because the stations or nodes in the system do not each store relative information.
In contrast, so called opportune routing techniques exploit opportunities that fluctuations in the network provide. In the context of wireless routing in particular, overall system performance degrades when quality of links within the system varies rapidly over time (for example, due to Rayleigh fading). However, opportune routing partially offsets this loss of performance by using the windows or peaks of opportunity that the variations also provide. When opportune routing is employed, there is not a single route for each source-destination node pair. Instead data packets follow a route that is somewhat random, leading from the source node to the destination node. Consequently, when Bellman-Ford is used, consecutive packets will be sent over the same route, whereas when opportune routing is used, consecutive packets can be routed over different paths but in the same general direction. However, also opportune routing protocols are based on an underlying route/cost determination protocol such as Bellman-Ford, as will be appreciated below.
For a source-destination node pair to be able to communicate with one another two functions have to be implemented, namely route determination (including route maintenance) and packet forwarding.
Firstly, in a route/cost determination step, routes must be determined for each source-destination node pair over which data packets will be sent (at least the next hop needs to be determined for each node). An exception is flooding which does not require knowledge about routes. The determined routes need to be disseminated to relevant nodes in all cases except source routing
Secondly, in a packet forwarding step, packets that are received at a node need to be forwarded to a next node along the route determined in the route determination step.
Route/Cost Determination
Routes are traditionally determined based on some shortest path criteria, which gives a single shortest path or route with respect to some cost for each source and destination node pair. The overall goal of such a method is generally stated as:
Given a network of nodes connected by links, where each link has a cost associated with it, define the cost of a path between two nodes as the sum of the costs of the links traversed. For each pair of nodes, find the path with the least cost.
The Bellman-Ford algorithm has played a central role in wired networks (e.g. Internet), but also has an important function in wireless multihop systems. The algorithm provides shortest path determination in a distributed and uncoordinated fashion and guarantees convergence within a finite time by merely exchanging information between adjacent neighbors. Equivalent to shortest path one can use the term minimum cost path/route, which emphasizes that the path is a minimum path with respect to some particular cost metric.
Since Bellman-Ford is a good example of a shortest path algorithm, it will be briefly described with reference to FIG. 1A. But first some definitions that will be useful. Let S be the set of all nodes in the network. Let d denote the destination node for which the route determination algorithm determines routes to. Node i is the node under consideration, i.e. which tries to determine how to get to node d. Now, let S′ define the set of all nodes which node i is able to communicate with, i.e. so called neighbor nodes. Nodes within the set S′ are indexed by j in the range 1 to J. S″ is then a trivial set containing the node from the set S′ that from i's viewpoint yields the shortest path. Under the assumption that shortest path is calculated in terms of hops, one node is appointed to belong to S″. The shortest path goes over L1 to the node in S″.
In order to determine the next hop node S″ on a packet's minimum path or route towards the destination node d and the cost of reaching the destination node (i.e. the cost of node i, Costid), the algorithm or method has to consider the costs Costij to reach the nodes in S′, as well as the costs Costjd from there on onwards to the destination node d.
The basic Bellman-Ford algorithm can then be described as follows:
Initially,Costid=∞ and Costdd=0
The costs are then calculated according to
      Cost    id    =            min              ∀                  j          ∈                      S            ′                                ⁢          (                        Cost          ij                +                  Cost          jd                    )      
This provides the following two important outputsCostid and S″
Hence, one knows were to forward packets as well as the cost for doing so, and this information needs to be distributed to surrounding nodes.
The algorithm in words: A destination node d initiates the shortest path calculation by broadcasting an initial cost (of e.g. 0) to the adjacent nodes which all have infinite cost for the destination node d to start with. Each node then calculates their respective cost and distributes the result to the neighboring nodes. As more cost information is received, new and lower values of cost are calculated and distributed. After some finite time, all nodes have assumed their lowest attainable cost. If multiple routes with the same cost exist, one of the routes is selected for example by random.
As data is later received at a node, it is forwarded over the lowest cost route according to the destination address. An important observation is that there is at most one next hop node for each destination at any time instants.
Examples of possible cost metrics are: number of hops, delay, interference, power consumption, link capacity etc. Note that the metric does not need to be additive, one may use other operations. Furthermore the min operation may be changed to a max operation instead. One example involving those two issues could be to determine the most reliable route as:
      Reliability    id    =            max              ∀                  j          ∈                      S            ′                                ⁢          (                        Reliability          ij                ·                  Reliability          jd                    )      Packet Forwarding
Traditional packet forwarding based on the Bellman-Ford algorithm is trivial in the sense that there is only one next hop choice.
Other forwarding protocols like Cisco's IGRP [1], Random forward routing [2], Opportune routing [3, 4], Selection Diversity Forwarding [5], and Anycast [6] enables a node to send a received packet to one out of several optional nodes. The forwarding process therefore involves a non-trivial choice to be made amid a set of favorable nodes. Let us here denote those schemes forward decision based routing, FDBR. This is routing in its most adaptive form, i.e. taking an adaptive decision at each forwarding instance.
In IGRP [1], a node forwards packets to any node having a cost at most v times the minimum cost determined by the Bellman-Ford algorithm.
Random forward routing [2] means that packets are sent to a random node in the forward direction based either on cost from Bellman-Ford or position.
Opportune-routing [3, 4] exploits a Bellman-Ford algorithm to acquire a notion of general correct direction of forwarding and adds local and current knowledge of e.g. link quality and node availability in the forwarding selection.
Selection Diversity Forwarding (SDF) [5] postpones the routing decision to after a packet has been multicast to a multitude of candidate relay nodes. Based on responses and informed node status the sending station selects and informs one of the candidate stations or nodes that successfully received earlier packet transmission. The next hop node determination algorithm is orthogonal to the SDF mechanism, but may be based on e.g. the Bellman-Ford algorithm.
Anycast [6] transmits a probe prior to any data transmission and therefore near identical operation to the basic SDF will be experienced. In addition, Anycast is similar to a variant of SDF.
Note that there is a distinct difference between this somewhat multipath oriented routing scheme and classical multipath routing. In the latter case, multiple and parallel routes are defined for source destination node pairs, where the forwarding choice is merely performed at the source, i.e. disjoint multipath routing. As packets are led into one of the multiple routes, they then follow their chosen route and hence the forwarding decision is trivial as in the classical Bellman-Ford case.
In addition to route determination and packet forwarding, an optional function is to incorporate topology control that aims to provide suitable connectivity in the network. This enhances performance and saves resources. Topology control typically includes power control and link adaptation.